//给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
//
// 请你找出符合题意的 最短 子数组，并输出它的长度。
//
//
//
//
//
// 示例 1：
//
//
//输入：nums = [2,6,4,8,10,9,15]
//输出：5
//解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
//
//
// 示例 2：
//
//
//输入：nums = [1,2,3,4]
//输出：0
//
//
// 示例 3：
//
//
//输入：nums = [1]
//输出：0
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 10⁴
// -10⁵ <= nums[i] <= 10⁵
//
//
//
//
// 进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？
//
//
// Related Topics 栈 贪心 数组 双指针 排序 单调栈 👍 778 👎 0

package leetcode.editor.cn;


import java.util.Arrays;

@SuppressWarnings("all")
//Java：最短无序连续子数组
public class 最短无序连续子数组 {
    public static void main(String[] args) {
        Solution solution = new 最短无序连续子数组().new Solution();
        // TO TEST
        int[] nums = {1, 3, 4, 5, 2};
        System.out.println(solution.findUnsortedSubarray(nums));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findUnsortedSubarray(int[] nums) {
            int n = nums.length;
            int maxn = Integer.MIN_VALUE, right = -1;
            int minn = Integer.MAX_VALUE, left = -1;
            for (int i = 0; i < n; i++) {
                if (maxn > nums[i]) {
                    right = i;
                } else {
                    maxn = nums[i];
                }
                if (minn < nums[n - i - 1]) {
                    left = n - i - 1;
                } else {
                    minn = nums[n - i - 1];
                }
            }
            return right == -1 ? 0 : right - left + 1;

        }

        private int qsort(int[] nums) {
            if (nums.length <= 1)
                return 0;
            if (isSorted(nums))
                return 0;

            int[] cp = new int[nums.length];
            System.arraycopy(nums, 0, cp, 0, cp.length);
            Arrays.sort(nums);
            int i = 0, j = cp.length - 1;
            while (cp[i] == nums[i]) {
                i++;
            }
            while (cp[j] == nums[j]) {
                j--;
            }

            return j - i + 1;
        }

        public void swap(int[] arr, int index1, int index2) {
            int temp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = temp;
        }

        private boolean isSorted(int[] nums) {

            for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i + 1] < nums[i])
                    return false;
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}
